package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1043 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxSumAfterPartitioning(int[] arr, int k) {
            int[] dp = new int[arr.length];
            int prevJMax = Integer.MIN_VALUE;

            for (int i = 0; i < k; i++) {
                prevJMax = Math.max(prevJMax, arr[i]);
                dp[i] = (i + 1) * prevJMax;
            }

            for (int i = k; i < arr.length; i++) {
                prevJMax = arr[i];
                for (int j = 1; j <= k; j++) {
                    prevJMax = Math.max(prevJMax, arr[i - j + 1]);
                    dp[i] = Math.max(dp[i], dp[i - j] + j * prevJMax);
                }
            }

            return dp[arr.length - 1];
        }
    }

    public void run() {
        System.out.println(new Solution().maxSumAfterPartitioning(InputUtil.toIntegerArray("[1,15,7,9,2,5,10]"), 3));
        System.out.println(new Solution().maxSumAfterPartitioning(InputUtil.toIntegerArray("[1,4,1,5,7,3,6,1,9,9,3]"), 4));
        System.out.println(new Solution().maxSumAfterPartitioning(InputUtil.toIntegerArray("[1]"), 1));
    }

    public static void main(String[] args) throws Exception {
        LC1043 an = new LC1043();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
